package com.demo.study.algorithm.sorts;


import java.util.Arrays;

import static com.demo.study.utils.ArrayUtil.*;

/**
 * 快速排序-双边循环
 *
 * @author Baymax
 * @since 2024-08-16
 */
public class B07_QuickSort2 {
    public static void main(String[] args) {
        int[] nums = intRandomArray();
        printArray(nums);
        quickSort(nums);
        printArray(nums);

        Arrays.sort(nums);
    }

    /**
     * 快速排序-双边快排<p>
     * 核心思想：每轮找到一个基准点元素，把比它小的放到它的左边，比它大的放到它的右边，这称之为分区
     * <li>选择最左边元素作为基准点元素</li>
     * <li>j指针负责从右向左找到比基准点小的元素，i指针负责从左向右找比基准点大的元素</li>
     * <li>一旦找到，j和i二者交换</li>
     * <li>最后基准点与i交换（j也可以，此时二者相同），i即为分区位置</li>
     */
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(array, left, right); // p代表基准点元素的索引
        quick(array, left, p - 1);
        quick(array, p + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        int pv = array[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 1.j从右向左找小的 -- j要优先
            while (i < j && array[j] >= pv) {
                j--;
            }
            // 2.i从左向右找大的
            while (i < j && array[i] <= pv) {
                i++;
            }
            // 3.交换位置
            swap(array, i, j);
        }
        swap(array, left, i);
        return i;
    }

}
